/*-------------------------------------------------------------------------*/
/**
  @file		execrefine_core.c
  @author	Renaud Wanchoor
  @update date	March 2007 by Xiaochen Wu
  @brief	Reassignment Management

  This library provides function to deal with
  vertex reassignment
  - creation of various move heaps
  - insertion, deletion from the move heap and boundaries
  - update when a vertex is moved
  - undo recent move list
  
*/
/*--------------------------------------------------------------------------*/

#include "pagrid.h"
#include "execrefine_params.h"

static int  Heapify(RefCtrl* ctrl, int v,int from,int to);

/**
 * \brief insert a reassignment into both the move heap and boundaries
 *
 * compute information about a moving vertex v from from to to and
 * insert it into both boundaries and heap, need procs the weight of
 * edges that connect  v to processors
 *
 * \param ctrl uncoarsening ctrl structure
 * \param v vertex to be moved
 * \param from origin of v
 * \param to destination of v
 * \return 0 if the vertex was not inserted into the heap 1 otherwise
 */
int Heapify(RefCtrl* ctrl, int v,int from,int to){
  vRef*  rinfo;
  double deltaF,deltaT,deltaO;
  int    dOflag;

  Heap*           heap = ctrl->heap;
  int*           procs = ctrl->procs;
  int*          procon = ctrl->procon;
  FILTER_FN* filter_fn = ctrl->filter_fn;
  GAIN_FN*     gain_fn = ctrl->gain_fn;
  vRef**         rvtxs = ctrl->rvtxs;
  vRefCont*     proref = ctrl->proref;

  int*           gvwgt = ctrl->g->vwgt;

  int            nnpro = ctrl->n->npro;
  double**      nratio = ctrl->n->ratio;
  double*    nprospeed = ctrl->n->prospeed;      
  int**        connect = ctrl->n->connect;
  int**        latency = ctrl->n->latency;


  if(procs[to] == 0 || to == from)
    return 0;
 
  COMPUTEREFINFO(v,from,to,gvwgt,nprospeed,procs,procon,nnpro,nratio,connect,latency,
		 deltaF,deltaT,deltaO,dOflag);

  /* insert into boundaries */
  rinfo = CONT_Add(ctrl, proref + from,v,from,to,deltaF,deltaT,deltaO,dOflag);

  /* filter */
  if((* filter_fn)(ctrl,0,v,from,to,deltaF,deltaT,deltaO,dOflag) == 0)
    return 0;  

  /* insert into heap */
  rvtxs[ctrl->nrvtxs] = rinfo;
  HeapInsert(heap,(*gain_fn)(ctrl,rinfo));
  rinfo->pos = rvtxs + ctrl->nrvtxs;
  ctrl->nrvtxs++;    
  
  return 1;
}

/**
 * \brief Create a heap with all potential reassignment
 *
 * RefCtrl::heap is build according to boundary vertices that passe the 
 * filter, (no more used but i kept it anyway)
 *
 * \param ctrl uncoarsening ctrl structure
 */
void HeapifyAll(RefCtrl* ctrl){
  vRef* rvtx;
  int v_pos, from;

  vRefCont*     proref = ctrl->proref;
  Heap*           heap = ctrl->heap;
  vRef**         rvtxs = ctrl->rvtxs;
  FILTER_FN* filter_fn = ctrl->filter_fn;
  GAIN_FN*     gain_fn = ctrl->gain_fn;

  int            nnpro = ctrl->n->npro;  

  HeapClean(heap);  

  for(from=0;from<nnpro;from++){
      
    for(v_pos = 0;v_pos<proref[from].s;v_pos++){
      rvtx = proref[from].arr + v_pos;            
      
      if((* filter_fn)(ctrl,0,rvtx->idx,rvtx->from,rvtx->to,rvtx->deltaF,rvtx->deltaT,rvtx->deltaO,rvtx->dOflag) == 0)
	continue;
      
      /* heapify it */    
      rvtxs[ctrl->nrvtxs] = rvtx;
      HeapInsert(heap,(*gain_fn)(ctrl,rvtx));
      rvtx->pos = rvtxs + ctrl->nrvtxs;
      ctrl->nrvtxs++;
    }
  }  
}
/**
 * \brief Create a heap with all potential reassignment from a particular processor
 *
 * RefCtrl::heap is build according to boundary vertices that passe the 
 * filter
 *
 * \param ctrl uncoarsening ctrl structure
 * \param from processor which the vertices are moved from
 */
void HeapifyFrom(RefCtrl* ctrl,int from){  
  vRefCont*     proref = ctrl->proref;
  Heap*           heap = ctrl->heap;
  vRef**         rvtxs = ctrl->rvtxs;
  FILTER_FN* filter_fn = ctrl->filter_fn;
  GAIN_FN*     gain_fn = ctrl->gain_fn;
  
  vRef* rvtx;
  int v_pos;

  HeapClean(heap);  
  
  for(v_pos = 0;v_pos<proref[from].s;v_pos++){
    rvtx = proref[from].arr + v_pos;
       
    /* heap filter */       
    if((* filter_fn)(ctrl,0,rvtx->idx,rvtx->from,rvtx->to,rvtx->deltaF,rvtx->deltaT,rvtx->deltaO,rvtx->dOflag) == 0)
      continue;

    /* heapify it */    
    rvtxs[ctrl->nrvtxs] = rvtx;
    HeapInsert(heap,(*gain_fn)(ctrl,rvtx));
    rvtx->pos = rvtxs + ctrl->nrvtxs;
    ctrl->nrvtxs++;
  }    
}

/**
 * \brief Create a heap with all potential reassignment to a particular processor
 *
 * RefCtrl::heap is build according to boundary vertices that passe the 
 * filter
 *
 * \param ctrl uncoarsening ctrl structure
 * \param to processor which the vertices are moved to
 */
void HeapifyTo(RefCtrl* ctrl,int to){
  int        from,i,istart,iend,v_pos;
  vRef*      rvtx;

  vRefCont*     proref = ctrl->proref;  
  Heap*           heap = ctrl->heap;  
  vRef**         rvtxs = ctrl->rvtxs;
  FILTER_FN* filter_fn = ctrl->filter_fn;
  GAIN_FN*     gain_fn = ctrl->gain_fn;

  int*       appadjidx = ctrl->n->app->adjidx;
  int*       appadjncy = ctrl->n->app->adjncy;
  int*         apprpro = ctrl->n->rpro;
  int*          apppro = ctrl->n->app->pro;

  HeapClean(heap);  

  /* use processor connectivity graph in the application to find out
     neighbors of processor to */
  istart = appadjidx[apprpro[to]];
  iend   = appadjidx[apprpro[to]+1];

  for(i=istart;i<iend;i++){
    from = apppro[appadjncy[i]];
    
    for(v_pos = 0;v_pos<proref[from].s;v_pos++){
      rvtx = proref[from].arr + v_pos;
      if(rvtx->to != to)
	continue;           

      /* heap filter */    
      if((* filter_fn)(ctrl,0,rvtx->idx,rvtx->from,rvtx->to,rvtx->deltaF,rvtx->deltaT,rvtx->deltaO,rvtx->dOflag) == 0)
	continue;

      /* heapify it */
      rvtxs[ctrl->nrvtxs] = rvtx;
      HeapInsert(heap,(*gain_fn)(ctrl,rvtx));
      rvtx->pos = rvtxs + ctrl->nrvtxs;
      ctrl->nrvtxs++;
    }  
  }  
}

/**
 * \brief undo the recent move list
 *
 * \param ctrl uncoarsening ctrl structure
 */
void UndoRecentMoves(RefCtrl* ctrl){
  int   undo_pos,idx,to,from;
  vRef* rvtx;

  vRef* undo = ctrl->undo;  
    
  for(undo_pos=ctrl->nb_undo-1;undo_pos>=0;undo_pos--){
    rvtx = undo + undo_pos;
    idx  = rvtx->idx;
    from = rvtx->from;
    to   = rvtx->to;
    

    /* compute procs for pheapupdate */
    if(rvtx->dOflag){
      int i,istart,iend,w,prow;
      int nnpro = ctrl->n->npro;
      int* procs = ctrl->procs;
      int* gadjidx = ctrl->g->adjidx;
      int* gadjncy = ctrl->g->adjncy;
      int* gadjwgt = ctrl->g->adjwgt;
      int* gpro    = ctrl->g->pro;
      
      for(i=0;i<nnpro;i++)
	procs[i] = 0;

      istart = gadjidx[idx];
      iend   = gadjidx[idx+1];

      for(i=istart;i<iend;i++){
	w = gadjncy[i];
	prow= gpro[w];

	if(prow == from || prow == to)
	  continue;
      
	procs[prow] += gadjwgt[i];      
      }       
    }       

    /* vertex was moved and then undo we dont count that as 
       active moves */
    ctrl->mvtxs[idx]-=2;

    /* undo the move */
    MOVE_NOUNDO(ctrl,rvtx);        
  }  
  ctrl->nb_undo = 0;
}

/**
 * \brief remove a vertex from boundaries and the move heap
 *
 * remove vertex vidx from both boundaries and heap if it belongs to
 * processor prov
 *
 * \param ctrl uncoarsening ctrl structure
 * \param v  vertex index
 * \param prov origin of v
 *
 */
void RemoveHeapEntry(RefCtrl* ctrl,int vidx,int pro){
  vRef*     rvtx;  
  vRef**    vheap;
  int       v_pos;

  vRefCont* proref = ctrl->proref;
  Heap*       heap = ctrl->heap;
  vRef**     rvtxs = ctrl->rvtxs;    

  for(v_pos = 0;v_pos < proref[pro].s;v_pos++){
    rvtx = proref[pro].arr + v_pos;    
    while(rvtx->idx == vidx){
      vheap = rvtx->pos;      
      
      /* if it is in the heap remove it */
      if(vheap != NULL){	
	HeapRemove(heap,vheap - rvtxs);
	AL_REM(vheap,rvtxs,ctrl->nrvtxs);
	
      }
      CONT_Rem(ctrl,proref + pro,rvtx);
    }
  }
}

/**
 * \brief update boundaries and the move heap when moving rvtx
 *
 * \param ctrl uncoarsening ctrl structure
 * \param rinfo refinement info of a reassignment
 * \param addundo boolean to tell if this reassignment could be undone
 */
void UpdateHeap(RefCtrl* ctrl,vRef* rinfo,int addundo){
  int i,istart,iend;
  int j,jstart,jend;
  int provv, vv=0;
  int _w, _prow;
  int k, l, update;
  int to_from, to_to, to_prow;
  int w,x,prox,new,vw_wgt=0,prow;
  vRef* vundo;  

  int     from = rinfo->from;
  int       to = rinfo->to;
  int        v = rinfo->idx;  
  
  int*   procs = ctrl->procs;
  int*  procon = ctrl->procon;
  int*  vprocs = ctrl->procs2;
  int* vprocon = ctrl->procon2;
  vRef*   undo = ctrl->undo;  

  int*    gpro = ctrl->g->pro;
  int* gadjidx = ctrl->g->adjidx;
  int* gadjncy = ctrl->g->adjncy;
  int* gadjwgt = ctrl->g->adjwgt;  
  int   gnvtxs = ctrl->g->nvtxs;

  int    nnpro = ctrl->n->npro;
  int** connect = ctrl->n->connect;
  int **convtxs = ctrl->n->convtxs;
  int **convtxs2 = ctrl->n->convtxs2;

  for(i=0;i<nnpro;i++){
    vprocs[i] = 0;
    vprocon[i] = 0;
  }

  istart = gadjidx[v];
  iend   = gadjidx[v+1];
  for(i=istart;i<iend;i++){
    w = gadjncy[i];
    prow = gpro[w];
    vprocon[prow]++;
  }

  /* Update gain heap for all the vertices adjacent to the moved vertex v */
  for(i=istart;i<iend;i++){
    w             = gadjncy[i];
    prow          = gpro[w];
    vw_wgt        = gadjwgt[i];
    vprocs[prow] += vw_wgt;    
 
    for(j=0;j<nnpro;j++){
      procs[j] = 0;
      procon[j] = 0;
    }
    
    jstart   = gadjidx[w];
    jend     = gadjidx[w+1];
    
    new = 1;
    for(j=jstart;j<jend;j++){
      x    = gadjncy[j];
      prox = gpro[x];
      
      if(prow != from){
        new = 0;
      }else{
        if(prox != prow && x != v){
	  new = 0;
        }
      }

      procs[prox] += gadjwgt[j];
      procon[prox]++;
    }        
    
    /* was already a boundary vertex */
    if(new == 0){            
      UpdateHeapEntry(ctrl,w,to);   
    /* is a new boundary */
    }else{   
      Heapify(ctrl,w,prow,to);  	
    }
  }

  /* Check whether there are other vertices needs to be updated besides the adjacent vertices of v */
  for(i = 0; i < nnpro; i++){
    /* processor i has connections to the moved vertex v and is not processor from or to */
    if(vprocon[i] > 0 && i != from && i != to){
      prow = i;
      /* Check whether processors prow and from lose connection, 
         if yes, the vertex that connects to from and prow concurrently has to update its gain heap 
         see gain_update1.bmp for explaination */
      if(connect[from][prow] == 0){
        for(vv = 0; vv < gnvtxs; vv++){
          provv = gpro[vv];
          if(provv != from && provv != prow){
            jstart = gadjidx[vv];
            jend = gadjidx[vv+1];
            to_from = 0;
            to_prow = 0;
            for(j = jstart; j < jend; j++){
              _w = gadjncy[j];
              _prow = gpro[_w];
              if(_prow == from){
                to_from = 1;
              }
              if(_prow == prow){
                to_prow = 1;
              }
            }
            if(to_from == 1 && to_prow == 1){
              UpdateHeapEntry_Con(ctrl, vv, from, prow);
            }
          }
        }
      }                 
      /* Check whether processors prow and to have connection,
         if yes, the vertex that connects from and prow concurrently has to update its gain heap
         the same reason as from and prow lose connection */
      if(connect[to][prow] == vprocon[prow]){
        for(vv = 0; vv < gnvtxs; vv++){
          provv = gpro[vv];
          if(provv != to && provv != prow){
            jstart = gadjidx[vv];
            jend = gadjidx[vv+1];
            to_to = 0;
            to_prow = 0;
            for(j = jstart; j < jend; j++){
              if(_prow == to){
                to_to = 1;
              }
              if(_prow == prow){
                to_prow = 1;
              }
            }
            if(to_to == 1 && to_prow == 1){
              UpdateHeapEntry_Con(ctrl, vv, to, prow);
            }
          }
        }
      } 
    }
  }

  /* Check whether processors from and to lose connection 
     if yes, the vertex that connects from and to concurrently has to update its gain heap
     the same reason as the previous example */
  if(connect[from][to] == 0){
    for(vv = 0; vv < gnvtxs; vv++){
      provv = gpro[vv];
      if(provv != from && provv != to){
        jstart = gadjidx[vv];
        jend = gadjidx[vv+1];
        to_from = 0;
        to_to = 0;
        for(j = jstart; j < jend; j++){
          _w = gadjncy[j];
          _prow = gpro[_w];
          if(_prow == from){
            to_from = 1;
          }
          if(_prow == to){
            to_to = 1;
          }
        }
        if(to_from == 1 && to_to == 1){
          UpdateHeapEntry_Con(ctrl, vv, from, to);
        }
      }
    }
  }

  /* if only one boundary vertex left from processor from to processor to 
     that boundary vertex has to update its gain because it move will affect the connection between processors */
  if(convtxs[from][to] == 1){
    for(vv = 0; vv < gnvtxs; vv++){
      provv = gpro[vv];
      if(provv == from){
        istart = gadjidx[vv];
        iend = gadjidx[vv+1];
        for(i = istart; i < iend; i++){
          x = gadjncy[i];
          prox = gpro[x];
          if(prox == to){
            UpdateHeapEntry_Vertex(ctrl, vv);
            break;
          }
        }
      }
    }
  }

  /* if only one boundary vertex left from processor to to processor from 
     that boundary vertex has to update its gain because it move will affect the connection between processors */
  if(convtxs[to][from] == 1){
    for(vv = 0; vv < gnvtxs; vv++){
      provv = gpro[vv];
      if(provv == to){
        istart = gadjidx[vv];
        iend = gadjidx[vv+1];
        for(i = istart; i < iend; i++){
          x = gadjncy[i];
          prox = gpro[x];
          if(prox == from){
            UpdateHeapEntry_Vertex(ctrl, vv);
            break;
          }
        }
      }
    }
  }

  /* check other possible gain update */
  for(k = 0; k < nnpro; k++){
    for(l = 0; l < nnpro; l++){
      if((k == from && l == to) || (k == to && l == from))
        continue;
      /* if the number of boundary vertices from k to l downs to 1, 
         the boundary vertex in k to l has to update its gain */
      if(convtxs[k][l] == 1 && convtxs2[k][l] > 1){
        for(vv = 0; vv < gnvtxs; vv++){
          provv = gpro[vv];
          if(provv != k || v == vv)
            continue;
          jstart = gadjidx[vv];
          jend = gadjidx[vv+1];
          for(j = jstart; j < jend; j++){
            x = gadjncy[j];
            prox = gpro[x];
            if(prox == l && x != v){
              UpdateHeapEntry_Vertex(ctrl, vv);
              break;
            }
          }
        }
      }
      /* if the number of boundary vertices from k to l increases from 0 to more than 1,
         the vertices connecting k and l concurrently has to update the gain */
      if(convtxs[k][l] >= 1 && convtxs2[k][l] == 0){
        for(vv = 0; vv < gnvtxs; vv++){
          provv = gpro[vv];
          if(provv == k || provv == l)
            continue;
          to_from = 0;
          to_to = 0;
          istart = gadjidx[vv];
          iend = gadjidx[vv+1];
          for(i = istart; i < iend; i++){
            x = gadjncy[i];
            prox = gpro[x];
            if(prox == k)
              to_from = 1;
            if(prox == l)
              to_to = 1;
          }
          if(to_from == 1 && to_to == 1){
            UpdateHeapEntry_Con(ctrl, vv, k, l);
          }
        }
      }
      /* if the number of boundary vertices from k to l increases from no larger than 1 to lager than 1
         the boundary vertices have to update gain */
      if(convtxs[k][l] > 1 && convtxs2[k][l] <= 1){
        for(vv = 0; vv < gnvtxs; vv++){
          provv = gpro[vv];
          if(provv != k || vv == v)
            continue;
          istart = gadjidx[vv];
          iend = gadjidx[vv+1];
          update = 0;
          for(i = istart; i < iend; i++){
            x = gadjncy[i];
            prox = gpro[x];
            if(prox == l && x != v){
              UpdateHeapEntry_Vertex(ctrl, vv);
              break;
            }
          }
        }
      }
    }
  }

  for(i = 0; i < nnpro; i++)
    for(j = 0; j < nnpro; j++)
      convtxs2[i][j] = convtxs[i][j];

  /* v is moved from processor from so
     remove v from from boundaries */
  RemoveHeapEntry(ctrl,v,from);
  
  /* v is moved to processor to so
     add v to to boundaries of to and undo move to undo list */  
  memcpy(procs,vprocs,nnpro*sizeof(int));  
  memcpy(procon,vprocon,nnpro*sizeof(int));
  vundo = NULL;

  
#if MOVE_ONCE
  ctrl->mvtxs[v]++;
#endif
  vundo = AddHeapEntry(ctrl,v,to,from);

  if(addundo){
    ERROR((ctrl->nb_undo>=MAX_KLMOVES,"recent move list is full\n"));
    /* special case v was an island 
       so it is no more connected to processor from 
       so you should not be able to move it to from
       well sometimes we need to */
    if(vundo == NULL){ 
      double   deltaF,deltaT,deltaO;
      int      dOflag;
      int*     gvwgt    = ctrl->g->vwgt;
      double*  nprospeed = ctrl->n->prospeed;
      double** nratio    = ctrl->n->ratio;
      int**    connect   = ctrl->n->connect;
      int**    latency   = ctrl->n->latency; 
      
      COMPUTEREFINFO(v,to,from,gvwgt,nprospeed,procs,procon,nnpro,nratio,connect,latency,
		     deltaF,deltaT,deltaO,dOflag);  
      undo[ctrl->nb_undo].pos     = NULL;
      undo[ctrl->nb_undo].idx     = v;
      undo[ctrl->nb_undo].from    = to;
      undo[ctrl->nb_undo].to      = from;
      undo[ctrl->nb_undo].deltaF  = deltaF;
      undo[ctrl->nb_undo].deltaT  = deltaT;
      undo[ctrl->nb_undo].deltaO  = deltaO;
      undo[ctrl->nb_undo].dOflag  = dOflag;
      DLA_INIT(undo + ctrl->nb_undo);            
      ctrl->nb_undo++;
    }else{
      undo[ctrl->nb_undo++] = *vundo;
    }
  }        
}

/**
 * \brief add a vertex to boundaries
 *
 * add vertex v into boundaries of processor proc and return the
 * pointer to the information of the move of v from proc to dest
 *
 * \param ctrl uncoarsening ctrl structure
 * \param v vertex index to be inserted into boundaries
 * \param proc processor index
 * \param dest destination processor index
 */
vRef* AddHeapEntry(RefCtrl* ctrl,int vidx,int pro,int destreturn){
  int i;
  vRef* rret = NULL;
  vRef* radd;

  int* procs = ctrl->procs;

  int  nnpro = ctrl->n->npro;  
  
  for(i=0;i<nnpro;i++){    
    if(procs[i] == 0 || i == pro)
      continue;
    radd = VREF_AddBnd(ctrl,vidx,pro,i);
    if(i == destreturn)
      rret = radd;
  }  
  return rret;
}
/**
 * \brief update information of vertex v into both boundaries and the move heap
 *
 * when a vertex w is moved from processor from to processor movedto
 * its neighbors (vertex v) need to be updated, this is what this
 * function does. Movedto is required because it might be a new
 * destination for vertex v. ctrl->procs is used and must represent the
 * sum of edge weights that connect v to processors.
 *
 * \param ctrl uncoarsening ctrl structure
 * \param v vertex index to be updated
 * \param movedto destination of reassignment
 */
void UpdateHeapEntry(RefCtrl* ctrl,int vidx,int movedto){
  int vto,flagto = 0; 
  vRef* rinfo;
  vRef** vheap;

  GAIN_FN*  gain_fn = ctrl->gain_fn;  
  Heap*        heap = ctrl->heap;
  int*        procs = ctrl->procs;
  int*       procon = ctrl->procon;
  vRef**      rvtxs = ctrl->rvtxs;
  vRefCont*  proref = ctrl->proref;
  vRef*        bnds = ctrl->bnds;
  

  int*         gvwgt = ctrl->g->vwgt;
  int*          gpro = ctrl->g->pro;

  int          nnpro = ctrl->n->npro;
  double**    nratio = ctrl->n->ratio;
  double*  nprospeed = ctrl->n->prospeed;
  int**      connect = ctrl->n->connect;
  int**      latency = ctrl->n->latency;
  
  int          vfrom = gpro[vidx];    

  rinfo = DLA_START(bnds + vidx);

  do{
    vto   = rinfo->to;
    vheap = rinfo->pos;
 
    flagto = (flagto || vto == movedto);    

    /* removing part if reassignment disconnect vertex to its destination */
    if(procs[vto] == 0){
      /* was in the heap remove it from the heap */
      if(vheap != NULL){
	ERROR((*vheap != rinfo,"Updateheapentry error code 1\n"));
	HeapRemove(heap,vheap - rvtxs);
	AL_REM(vheap,rvtxs,ctrl->nrvtxs);	  
      }
      /* remove it from boundaries */
      rinfo = CONT_Rem(ctrl,proref + vfrom,rinfo);
    }else{
      /* update vertex */
      COMPUTEREFINFO(vidx,vfrom,vto,gvwgt,nprospeed,procs,procon,nnpro,nratio,connect,latency,
		     rinfo->deltaF,rinfo->deltaT,rinfo->deltaO,rinfo->dOflag);
      
      /* update heap */
      if(vheap != NULL){
	HeapUpdate(heap,vheap - rvtxs,(*gain_fn)(ctrl,rinfo)); 
      }
      rinfo = DLA_NEXT(rinfo);
    }  
  }while(!DLA_IS_END(bnds + vidx,rinfo));
  
  /* the vertex that is being updated is neighbor to the vertex being moved 
     if the vertex was not already connected to the destination of the reas
     signment it is inserted into boundaries and heap */
  if(flagto == 0 && vfrom != movedto){
    Heapify(ctrl,vidx,vfrom,movedto);        
  }
}

/**
 * \brief update gain information of vertex vidx to movedto1 and movedto2
 *
 * when a pair of processors loses connection, or becomes connected
 * the gain of a vertex on other processors connecting to the pair 
 * of the processors concurrently also changed. 
 * This function updates this gain information
 *
 * \param ctrl uncoarsening ctrl structure
 * \param vidx vertex index to be updated
 * \param movedto1 destination of reassignment
 * \param movedto2 destination of reassignment
 */
void UpdateHeapEntry_Con(RefCtrl* ctrl,int vidx,int movedto1, int movedto2){
  int vto = 0; 
  int i, istart, iend;
  int w, prow;
  vRef* rinfo;
  vRef** vheap;

  GAIN_FN*  gain_fn = ctrl->gain_fn;  
  Heap*        heap = ctrl->heap;
  int*        procs = ctrl->procs;
  int*       procon = ctrl->procon;
  vRef**      rvtxs = ctrl->rvtxs;
  vRef*        bnds = ctrl->bnds;
  

  int*         gvwgt = ctrl->g->vwgt;
  int*          gpro = ctrl->g->pro;
  int*       gadjidx = ctrl->g->adjidx;
  int*       gadjncy = ctrl->g->adjncy;
  int*       gadjwgt = ctrl->g->adjwgt;

  int          nnpro = ctrl->n->npro;
  double**    nratio = ctrl->n->ratio;
  double*  nprospeed = ctrl->n->prospeed;
  int**      connect = ctrl->n->connect;
  int**      latency = ctrl->n->latency;
  
  int          vfrom = gpro[vidx];    

  rinfo = DLA_START(bnds + vidx);
 
  for(i = 0; i < nnpro; i++){
    procs[i] = 0;
    procon[i] = 0;
  }
  istart = gadjidx[vidx];
  iend = gadjidx[vidx+1];
  for(i = istart; i < iend; i++){
    w = gadjncy[i];
    prow = gpro[w];
    procs[prow] += gadjwgt[i];
    procon[prow]++;
  }
  
  do{
    vto   = rinfo->to;
    vheap = rinfo->pos;
  
    if(vto == movedto1 || vto == movedto2){

      /* update vertex */
        COMPUTEREFINFO(vidx,vfrom,vto,gvwgt,nprospeed,procs,procon,nnpro,nratio,connect,latency,
		     rinfo->deltaF,rinfo->deltaT,rinfo->deltaO,rinfo->dOflag);
      
      /* update heap */
        if(vheap != NULL){
          HeapUpdate(heap,vheap - rvtxs,(*gain_fn)(ctrl,rinfo)); 
        }
      }
      rinfo = DLA_NEXT(rinfo);  
  }while(!DLA_IS_END(bnds + vidx,rinfo));
}

/**
 * \brief update gain information of vertex vidx
 *
 * when there is only one vertex (vidx) is the boundary vertex from
 * processor from to processor to, the gain information of vertex vidx
 * has to be updated. 
 *
 * \param ctrl uncoarsening ctrl structure
 * \param vidx vertex index to be updated
 */
void UpdateHeapEntry_Vertex(RefCtrl* ctrl,int vidx){
  int vto = 0;
  int i, istart, iend;
  int w, prow;
  vRef* rinfo;
  vRef** vheap;

  GAIN_FN*  gain_fn = ctrl->gain_fn;
  Heap*        heap = ctrl->heap;
  int*        procs = ctrl->procs;
  int*       procon = ctrl->procon;
  vRef**      rvtxs = ctrl->rvtxs;
  vRef*        bnds = ctrl->bnds;


  int*         gvwgt = ctrl->g->vwgt;
  int*          gpro = ctrl->g->pro;
  int*       gadjidx = ctrl->g->adjidx;
  int*       gadjncy = ctrl->g->adjncy;
  int*       gadjwgt = ctrl->g->adjwgt;

  int          nnpro = ctrl->n->npro;
  double**    nratio = ctrl->n->ratio;
  double*  nprospeed = ctrl->n->prospeed;
  int**      connect = ctrl->n->connect;
  int**      latency = ctrl->n->latency;

  int          vfrom = gpro[vidx];

  rinfo = DLA_START(bnds + vidx);

  for(i = 0; i < nnpro; i++){
    procs[i] = 0;
    procon[i] = 0;
  }
  istart = gadjidx[vidx];
  iend = gadjidx[vidx+1];
  for(i = istart; i < iend; i++){
    w = gadjncy[i];
    prow = gpro[w];
    procs[prow] += gadjwgt[i];
    procon[prow]++;
  }
  do{
    vto   = rinfo->to;
    vheap = rinfo->pos;

        COMPUTEREFINFO(vidx,vfrom,vto,gvwgt,nprospeed,procs,procon,nnpro,nratio,connect,latency,
                     rinfo->deltaF,rinfo->deltaT,rinfo->deltaO,rinfo->dOflag);
      /* update heap */
        if(vheap != NULL){
          HeapUpdate(heap,vheap - rvtxs,(*gain_fn)(ctrl,rinfo));
        }
      rinfo = DLA_NEXT(rinfo);
  }while(!DLA_IS_END(bnds + vidx,rinfo));
}

/**
 * \brief update the processor heap according the reassignment rinfo
 *
 * \param ctrl uncoarsening ctrl structure
 * \param rinfo information of a reassignment
 */
void UpdatePHeap(RefCtrl* ctrl,vRef* rinfo){
  int i, istart, iend;
  int x, prox;
 
  int           v = rinfo->idx; 
  int        from = rinfo->from;
  int          to = rinfo->to;
  double   deltaF = rinfo->deltaF;
  double   deltaT = rinfo->deltaT;
  double   deltaO = rinfo->deltaO;
  int      dOflag = rinfo->dOflag;

  Heap*     pheap = ctrl->pheap;
  int*      procs = ctrl->procs;
  int*     procon = ctrl->procon;

  int       nnpro = ctrl->n->npro;
  double*   nexec = ctrl->n->exec;  
  double** nratio = ctrl->n->ratio;  
  int**   connect = ctrl->n->connect;
  int**   latency = ctrl->n->latency;

  int*       gpro = ctrl->g->pro;
  int*    gadjidx = ctrl->g->adjidx;
  int*    gadjncy = ctrl->g->adjncy;
  int*    gadjwgt = ctrl->g->adjwgt;


  for(i = 0; i < nnpro; i++){
    procs[i] = 0;
    procon[i] = 0;
  }
  
  istart = gadjidx[v];
  iend = gadjidx[v+1];
  for(i = istart; i < iend; i++){
    x = gadjncy[i];
    prox = gpro[x];
    procs[prox] += gadjwgt[i];
    procon[prox]++;
  }

  if(dOflag){
    for(i=0;i<nnpro;i++){
      if(i == from || i == to || procs[i] == 0)
	continue;
      nexec[i] += procs[i] * (nratio[i][to] - nratio[i][from]);
      if(connect[to][i] == procon[i] && connect[to][i] != 0){
        nexec[i] += latency[i][to];
      }
      if(connect[from][i] == 0 && connect[i][from] == 0){
        nexec[i] -= latency[i][from];
      }
      HeapUpdate(pheap,i,nexec[i]);
    }    
  }
  
  ctrl->t += deltaF + deltaT + deltaO;
  
  nexec[from] += deltaF;
  HeapUpdate(pheap,from,nexec[from]);
  nexec[to]   += deltaT;
  HeapUpdate(pheap,to,nexec[to]);

  ctrl->tmax = 0;
  for(i=0;i<nnpro;i++){
    if(ctrl->tmax<nexec[i])
      ctrl->tmax = nexec[i];
  }

  ctrl->tmean = ctrl->t/nnpro;
  ctrl->im    = nnpro*ctrl->tmax/ctrl->t;

}

/**
 * \brief update connection information of a vertex move
 *
 * when a vertex w is moved from processor from to processor to
 * the numbers of edges and boundary vertices between each pair of processors
 * are also changed. 
 * This function updates this change.
 *
 * \param ctrl uncoarsening ctrl structure
 * \param rinfo information of a reassignment
 */
void UpdateConnect(RefCtrl* ctrl, vRef* rinfo){
  int            v = rinfo->idx;
  int         from = rinfo->from;
  int           to = rinfo->to;
  
  int**    connect = ctrl->n->connect;
  int    **convtxs = ctrl->n->convtxs;
  int     *conproc = ctrl->n->conproc;
  int*      procon = ctrl->procon;
  int         npro = ctrl->n->npro;

  int i, istart, iend;
  int j, jstart, jend;
  int w, prow, x, prox, k;
  int* gadjidx = ctrl->g->adjidx;
  int* gadjncy = ctrl->g->adjncy;
  int* gpro = ctrl->g->pro;

  istart = gadjidx[v];
  iend = gadjidx[v+1];
  for(i = 0; i < npro; i++){
    procon[i] = 0;
  }
  for(i = istart; i < iend; i++){
    w = gadjncy[i];
    prow = gpro[w];
    procon[prow]++;
  }

  connect[from][to] -= procon[to];
  connect[from][to] += procon[from];
  connect[to][from] += procon[from];
  connect[to][from] -= procon[to];
  if(procon[to] > 0)
    convtxs[from][to]--;
  if(procon[from] > 0)
    convtxs[to][from]++;

  for(i = 0; i < npro; i++){
    if(i == from || i == to || procon[i] == 0)
      continue;
    connect[i][from] -= procon[i];
    connect[from][i] -= procon[i];
    connect[i][to] += procon[i];
    connect[to][i] += procon[i];
    convtxs[from][i]--;
    convtxs[to][i]++;
  }
  istart = gadjidx[v];
  iend = gadjidx[v+1];
  for(i = istart; i < iend; i++){
    w = gadjncy[i];
    prow = gpro[w];
    for(k = 0; k < npro; k++){
      conproc[k] = 0;
    }
    jstart = gadjidx[w];
    jend = gadjidx[w+1];
    for(j = jstart; j < jend; j++){
      x = gadjncy[j];
      if(x != v){
        prox = gpro[x];
        conproc[prox]++;
      }
    }
    if(conproc[from] == 0 && prow != from){
      convtxs[prow][from]--;
    }
    if(conproc[to] == 0 && prow != to){
      convtxs[prow][to]++;
    }
  }
}

/**
 * DEBUGING FUNCTION */
/*#ifdef DEBUGEXEC*/
int debugHeapNoPrint(RefCtrl* ctrl){
  int i,size=0;
  vRef* rvtx;
  
  Heap* heap       = ctrl->heap;
  vRef** rvtxs     = ctrl->rvtxs;
  GAIN_FN* gain_fn = ctrl->gain_fn;

  for(i=0;i<heap->s;i++){
    double gain = HeapGain(heap,i);
    int idx     = HeapPos(heap,i);
    
    if(idx == -1)
      break;
    
    size++;
    rvtx = rvtxs[idx];
    
    WARNING((*(rvtx->pos) != rvtx,"debugHeapNoprint : link error\n"),1);
    WARNING(((*gain_fn)(ctrl,rvtx) != gain,"debugHeapNoprint : gain error\n"),1);
  }

  WARNING((size != heap->s,"debugHeapNoPrint : size error (size %d heap->s %d)\n",size,heap->s),1);
  return 0;
}
/**
 * DEBUGING FUNCTION */
void debugHeap(RefCtrl* ctrl){
  int i;
  Heap* heap   = ctrl->heap;
  double* nexec = ctrl->n->exec;
  vRef** rvtxs = ctrl->rvtxs;
  vRef* rvtx;
  GAIN_FN* gain_fn     = ctrl->gain_fn;

  for(i=0;i<heap->s;i++){
    double gain = HeapGain(heap,i);
    int idx     = HeapPos(heap,i);
    
    if(idx == -1)
      break;

    rvtx = rvtxs[idx];
    
    printf("%2d %2d vtx : %2d, gain : %10.2f, from %2d(%10.2f) to %2d(%10.2f) dF %10.2f(%10.2f) dT %10.2f(%10.2f) dO %10.2f dE %10.2f\n",i,
	   
	   idx,rvtx->idx,gain,
	   rvtx->from,nexec[rvtx->from],
	   rvtx->to,nexec[rvtx->to],
	   rvtx->deltaF,nexec[rvtx->from]+rvtx->deltaF,rvtx->deltaT,nexec[rvtx->to]+rvtx->deltaT,rvtx->deltaO,
	   rvtx->deltaF+rvtx->deltaT+rvtx->deltaO);

    ERROR((*(rvtx->pos) != rvtx,"debugHeap : link error\n"));
    ERROR(((*gain_fn)(ctrl,rvtx) != gain,"debugHeap : gain error\n"));
  }

}

//#endif
/**
 * DEBUGING FUNCTION */
void debugExec(RefCtrl* ctrl){
  int i,istart,iend,j;
  int v,w,prov,prow;
  int provtxs;

  int nnpro        = ctrl->n->npro;
  double** nratio   = ctrl->n->ratio;
  int* pro         = ctrl->g->pro;
  int nvtxs        = ctrl->g->nvtxs;
  int* gvwgt        = ctrl->g->vwgt;
  int* gadjidx      = ctrl->g->adjidx;
  int* gadjncy      = ctrl->g->adjncy;
  int* gadjwgt      = ctrl->g->adjwgt;
  double* exec    = U_malloc(nnpro,double,"debugExec error code 1\n");
  double execsum  = 0;
  double execmax  = 0;
  double* nexec     = ctrl->n->exec;
  double* nprospeed = ctrl->n->prospeed;
  int error = 0;

  for(i=0;i<nnpro;i++)
    exec[i] = 0;

  for(v=0;v<nvtxs;v++){
    prov = pro[v];
    istart = gadjidx[v];
    iend   = gadjidx[v+1];

    exec[prov] += gvwgt[v]*nprospeed[prov];

    for(i=istart;i<iend;i++){
      w = gadjncy[i];
      prow = pro[w];
      
      if(prov == prow)
	continue;

      exec[prov] += gadjwgt[i]*nratio[prov][prow];     
    }
  }
  
  for(i=0;i<nnpro;i++){
    execsum += exec[i];
    if(exec[i]>execmax)
      execmax = exec[i];
  }

  printf("   %10s %10s\n","nexec","exec");
  printf("------------------------\n");
  for(i=0;i<nnpro;i++){
    provtxs = 0;
    error = error || (abs(nexec[i]-exec[i])>0.0001) || (abs(nexec[i])<0.0001);

    for(j=0;j<nvtxs;j++){
      if(pro[j] == i)
	provtxs++;
    }

    printf("%2d %10.2f %10.2f vtxs %d\n",i,nexec[i],exec[i],provtxs);
    
  }
  printf("\nsum : %10.2f sum2 : %10.2f\navg : %10.2f avg2 : %10.2f\nmax : %10.2f max2 : %10.2f\nim  : %10.8f im2  : %10.8f\n",
	 ctrl->t,execsum,
	 ctrl->tmean,execsum/nnpro,
	 ctrl->tmax,execmax,
	 ctrl->im,nnpro*execmax/execsum);
	 

  U_free("debugExec error code 2\n",&exec,LEND);
  ERROR((abs(ctrl->t-execsum)>0.0001,"debugExec error code 1 : sum not matching\n"));
  ERROR((abs(ctrl->tmean-execsum/nnpro)>0.0001,"debugExec error code 2 : avg not matching\n"));
  ERROR((abs(ctrl->tmax-execmax)>0.0001,"debugExec error code 3 : max not matching\n"));
  //ERROR((ctrl->im!=nnpro*execmax/execsum,"debugExec error code 1 : im not matching\n"));
  ERROR((error,"debugExec error code 4 : exec[i] not matching\n"));
  //getchar();
}
/************************** debug */
//#endif
/**
 * DEBUGING FUNCTION */
int debugExecNoPrint(RefCtrl* ctrl){
  int i,istart,iend,j;
  int v,w,prov,prow;
  int provtxs;

  int nnpro        = ctrl->n->npro;
  double** nratio   = ctrl->n->ratio;
  int* pro         = ctrl->g->pro;
  int nvtxs        = ctrl->g->nvtxs;
  int* gvwgt        = ctrl->g->vwgt;
  int* gadjidx      = ctrl->g->adjidx;
  int* gadjncy      = ctrl->g->adjncy;
  int* gadjwgt      = ctrl->g->adjwgt;
  double* exec    = ctrl->exec;
  double execsum  = 0;
  double execmax  = 0;
  double* nexec     = ctrl->n->exec;
  double* nprospeed = ctrl->n->prospeed;
  int** connect     = ctrl->n->connect;
  int** latency     = ctrl->n->latency;
  int error = 0;

  for(i=0;i<nnpro;i++)
    exec[i] = 0;

  for(v=0;v<nvtxs;v++){
    prov = pro[v];
    istart = gadjidx[v];
    iend   = gadjidx[v+1];

    exec[prov] += gvwgt[v]*nprospeed[prov];

    for(i=istart;i<iend;i++){
      w = gadjncy[i];
      prow = pro[w];
      
      if(prov == prow)
	continue;

      exec[prov] += gadjwgt[i]*nratio[prov][prow];     
    }
  }

  for(i = 0; i < nnpro; i++)
    for(j = 0; j < nnpro; j++)
      if(connect[i][j] > 0)
        exec[i] += latency[i][j];
  
  for(i=0;i<nnpro;i++){
    execsum += exec[i];
    if(exec[i]>execmax)
      execmax = exec[i];
  }

  for(i=0;i<nnpro;i++){
    provtxs = 0;
    error = error || (abs(nexec[i]-exec[i])>0.0001) || (abs(nexec[i])<0.0001);

    for(j=0;j<nvtxs;j++){
      if(pro[j] == i)
	provtxs++;
    }
  }

if(abs(ctrl->t-execsum) > 0.0001)
  printf("Sum is not match: ctrl->t is %f, and execsum is %f\n", ctrl->t, execsum);
if(abs(ctrl->tmean - execsum/nnpro) > 0.0001)
  printf("Average is not match: ctrl->tmean is %f, and execsum/nnpro is %f\n", ctrl->tmean, execsum/nnpro);
if(abs(ctrl->tmax-execmax)>0.0001)
  printf("Max is not match: ctrl->tmax is %f, and execmas is %f\n", ctrl->tmax, execmax);
if(error)
  for(i=0;i<nnpro;i++)
    printf("Exec is not match: ctrl->n->exec[%d] is %f, and exec[%d] is %f\n", i, nexec[i], i, exec[i]);
  
  WARNING((abs(ctrl->t-execsum)>0.0001,"debugExecNoPrint error code 1 : sum not matching\n"),0);
  WARNING((abs(ctrl->tmean-execsum/nnpro)>0.0001,"debugExecNoPrint error code 2 : avg not matching\n"),0);
  WARNING((abs(ctrl->tmax-execmax)>0.0001,"debugExecNoPrint error code 3 : max not matching\n"),0);
  //ERROR((ctrl->im!=nnpro*execmax/execsum,"debugExecNoPrint error code 1 : im not matching\n"));
  WARNING((error,"debugExecNoPrint error code 4 : exec[i] not matching\n"),0);
  //getchar();
  return 1;
}
